package com.leetcode.two_pointers.sliding_window;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dennis Li
 * @date 2020/9/23 14:29
 */
public class CheckInclution_567 {

    // 排列 -- 总之一定是连着的在一起 -- 是一个子串
    // 并且包含所有的字符
    public boolean checkInclusion(String s1, String s2) {
        // 先记录窗口的字符以及需求的字符
        Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        for (char c : s1.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        // valid记录有效字符，left和right用于构成滑动窗口
        int left = 0, right = 0, valid = 0;
        while (right < s2.length()) {
            char rc = s2.charAt(right);
            right++;
            if (need.containsKey(rc)) {
                window.put(rc, window.getOrDefault(rc, 0) + 1);
                // 如果超过了限定的字符数，此时有效字符不增加
                if (window.get(rc) <= need.get(rc))
                    valid++;
            }
            if (s1.length() == right - left) {
                // 子串中全部是有效字符
                if (valid == s1.length())
                    return true;
                char lc = s2.charAt(left);
                if (need.containsKey(lc)) {
                    int num = window.get(lc);
                    // 如果超过了规定的字符数，不需要减一
                    if (num <= need.get(lc))
                        valid--;
                    window.put(lc, num - 1);
                }
                left++;
            }
        }
        return false;
    }

}
